package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class IsSymmetric {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return isSymmetric(root.left,root.right);
    }

    private boolean isSymmetric(TreeNode left,TreeNode right){
        if (left!=null&&right==null){
            return false;
        }else if (left==null&&right!=null){
            return false;
        }else if (left==null&&right==null){
            return true;
        }else {
            return left.val==right.val&& isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
        }
    }


    public static   boolean isSymmetric1(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if (root==null){
            return true;
        }
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()){
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode==null&&rightNode==null){
                continue;
            }
            if (leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
                return false;
            }
            deque.offerFirst(leftNode.right);
            deque.offerFirst(leftNode.left);
            deque.offerLast(rightNode.left);
            deque.offerLast(rightNode.right);
        }
        return true;
    }

    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.offerFirst(1);
        deque.offerFirst(2);
        System.out.println(deque.size());
    }

}
